package aloge;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 后缀数组
 */
public class SuffixArray {

    public int[] suffixArray(String str) {
        // 暴力求解法，通过对所有的子串排序得到
        String[] strArrays = new String[str.length()];
        for (int i = 0; i < str.length(); i++) {
            strArrays[i] = str.substring(i);
        }
        Arrays.sort(strArrays);
        int[] rk = new int[str.length()];
        for (int i = 0; i < strArrays.length; i++) {
            rk[i] = str.length() - strArrays[i].length() + 1;
        }
        return rk;
    }

    public int[] suffixArray2(String str) {
        // 倍增排序
        Integer[] sa = new Integer[str.length() + 1];
        int[] rk = new int[(str.length() + 1) * 2];
        sa[0] = 0;
        for (int i = 1; i <= str.length(); i++) {
            sa[i] = i;
            rk[i] = str.charAt(i - 1);
        }
        for (int i = 1; i < str.length(); i *= 2) {
            // 对sa进行排序
            int k = i;
            Arrays.sort(sa, 1, str.length() + 1, (i1, i2) -> {
                // 比较两组数
                if (rk[i1] == rk[i2]) {
                    // 看哪个大
                    return rk[i1 + k] - rk[i2 + k];
                } else {
                    return rk[i1] - rk[i2];
                }
            });
            // 排序完成后，设置rk
            int[] oldRk = Arrays.copyOf(rk, rk.length);
            int p = 0;
            for (int j = 1; j <= str.length(); j++) {
                if (oldRk[sa[j]] == oldRk[sa[j - 1]] && oldRk[sa[j] + i] == oldRk[sa[j - 1] + i]) {
                    rk[sa[j]] = p;
                } else {
                    rk[sa[j]] = ++ p;
                }
            }
        }
        return Arrays.copyOfRange(rk, 1, str.length() + 1);
    }

    public int[] suffixArray3(String str) {
        int[] order = getOrder(str);
        int[] classes = computedCharClasses(str, order);
        int n = str.length();
        for (int i = 1; i < n; i<<=1) {
            order = getDoubledOrder(str, order, classes, i);
            classes = updateClasses(order, classes, i);
        }
        return order;
    }

    private int[] getDoubledOrder(String str, int[] order, int[] classes, int n) {
        // 不需要对第二关键词排序，只需要对第一关键词排序即可
        int[] counts = new int[str.length()];
        int[] newOrder = new int[str.length()];
        for (int i = 0; i < str.length(); i++) {
            counts[classes[i]] = counts[classes[i]] + 1;
        }
        for (int i = 1; i < str.length(); i++) {
            counts[i] = counts[i] + counts[i - 1];
        }
        for (int i = str.length() - 1; i >= 0; i--) {
            int start = (order[i] + str.length() - n) % str.length();
            int cl = classes[start];
            counts[cl] --;
            newOrder[counts[cl]] = start;
        }
        return newOrder;
    }

    private int[] updateClasses(int[] newOrder, int[] classfiy, int len) {
        int n = newOrder.length;
        int[] newClassfiy = new int[n];
        newClassfiy[newOrder[0]] = 0;
        for (int i = 1; i < n; i++) {
            int curr = newOrder[i];
            int prev = newOrder[i - 1];
            int mid = (curr + len) % n;
            int midPrev = (prev + len) % n;
            if (classfiy[curr] != classfiy[prev] || classfiy[mid] != classfiy[midPrev]) {
                newClassfiy[curr] = newClassfiy[prev] + 1;
            } else {
                newClassfiy[curr] = newClassfiy[prev];
            }
        }
        return newClassfiy;
    }

    private int[] getOrder(String str) {
        // 通过计数排序
        int[] counts = new int[128];
        int[] orders = new int[str.length()];
        for (int i = 0; i < str.length(); i++) {
            counts[str.charAt(i)] = counts[str.charAt(i)] + 1;
        }
        for (int i = 1; i < counts.length; i++) {
            counts[i] = counts[i] + counts[i - 1];
        }
        for (int i = str.length() - 1; i >= 0; i--) {
            counts[str.charAt(i)] --;
            orders[counts[str.charAt(i)]] = i;
        }
        return orders;
    }

    private int[] computedCharClasses(String str, int[] order) {
        int[] classes = new int[str.length()];
        classes[order[0]] = 0;
        for (int i = 1; i < str.length(); i++) {
            if (str.charAt(order[i]) != str.charAt(order[i - 1])) {
                classes[order[i]] = classes[order[i - 1]] + 1;
            } else {
                classes[order[i]] = classes[order[i - 1]];
            }
        }
        return classes;
    }

    public static void main(String[] args) {
        SuffixArray suffixArray = new SuffixArray();
        int[] array2 = suffixArray.suffixArray3("aabaaaab");
        for (int i : array2) {
            System.out.println(i);
        }
    }

}
